from collections import defaultdict
import sys
import time
from typing import Dict, Set, Tuple
class Relation(object):
    def __init__(self, pairs: Set[Tuple[str, str]]):
        self.images = defaultdict(set)  # type: Dict[str, Set[str]]
        self.preimages = defaultdict(set)  # type: Dict[str, Set[str]]
        for x, y in pairs:
            self.add(x, y)

    def add(self, x: str, y: str) -> None:
        self.images[x].add(y)
        self.preimages[y].add(x)

    def remove(self, x: str, y: str) -> None:
        if y in self.images[x]:
            self.images[x].remove(y)
        if x in self.preimages[y]:
            self.preimages[y].remove(x)

    def image(self, x: str) -> Set[str]:
        return self.images.get(x, set())

    def preimage(self, y: str) -> Set[str]:
        return self.preimages.get(y, set())


class Lattice(object):
    def __init__(self, links):
        self.concepts = set()
        self._relation = Relation([])
        for a, b in links:
            self.add_concept(a)
            self.add_concept(b)
            self.add_link(a, b)

    def parents(self, concept):
        return self._relation.preimage(concept)

    def children(self, concept):
        return self._relation.image(concept)

    def add_concept(self, concept):
        self.concepts.add(concept)

    def top(self):
        concept = next(iter(self.concepts))
        parents = self.parents(concept)
        while len(parents) > 0:
            concept = next(iter(parents))
            parents = self.parents(concept)
        return concept

    def bottom(self):
        concept = next(iter(self.concepts))
        children = self.children(concept)
        while len(children) > 0:
            concept = next(iter(children))
            children = self.children(concept)
        return concept

    def add_link(self, parent, child):
        self._relation.add(parent, child)

    def remove_link(self, parent, child):
        self._relation.remove(parent, child)

    def replace_concept(self, concept, new_concept):
        parents = self.parents(concept)
        children = self.children(concept)
        self.concepts.remove(concept)
        self.add_concept(new_concept)
        for parent in set(parents):
            self.remove_link(parent, concept)
            self.add_link(parent, new_concept)
        for child in set(children):
            self.remove_link(concept, child)
            self.add_link(new_concept, child)
    def __repr__(self):
        return repr(self._relation.images)


class Concept(object):
    def __init__(self, extent, intent):
        self.extent = frozenset(extent)
        self.intent = frozenset(intent)

    def __hash__(self):
        return hash((self.extent, self.intent))

    def __eq__(self, other):
        return self.__hash__() == other.__hash__()

    def __repr__(self):
        return repr((".".join(sorted(map(str, self.extent))), ".".join(sorted(map(str, self.intent)))))


def get_maximal_generator(intent, generator_concept, lattice):
    parent_is_maximal = True
    while parent_is_maximal:
        parent_is_maximal = False
        parents = lattice.parents(generator_concept)
        for parent in parents:
            if intent <= parent.intent:
                generator_concept = parent  # go up a level
                parent_is_maximal = True  # continue loop and check new generator's parents
    return generator_concept


def make_new_parents(parents, candidate):
    new_parents = set(parents)
    add_concept = True
    for concept in parents:
        if candidate.intent <= concept.intent:
            add_concept = False
            break
        elif concept.intent <= candidate.intent:
            new_parents.remove(concept)
    if add_concept:
        new_parents.add(candidate)
    return new_parents


def add_object_to_parents(obj: str, concept: Concept, lattice: Lattice) -> None:
    new_concept = Concept(concept.extent.union({obj}), concept.intent)
    lattice.replace_concept(concept, new_concept)
    parents = list(lattice.parents(concept))  # 避免在循环中多次调用
    for parent in parents:
        add_object_to_parents(obj, parent, lattice)

def add_intent(obj: str, intent: frozenset, generator_concept: Concept, lattice: Lattice) -> Concept:
    generator_concept = get_maximal_generator(intent, generator_concept, lattice)

    if generator_concept.intent == intent:
        return generator_concept

    generator_parents = list(lattice.parents(generator_concept))  # 避免在循环中多次调用
    new_parents = set()
    for candidate in generator_parents:
        if not candidate.intent < intent:
            candidate = add_intent(obj, candidate.intent.intersection(intent), candidate, lattice)
        new_parents = make_new_parents(new_parents, candidate)
    new_concept = Concept(generator_concept.extent.union({obj}), intent)
    lattice.add_concept(new_concept)
    for parent in new_parents:
        lattice.remove_link(parent, generator_concept)
        lattice.add_link(parent, new_concept)
    lattice.add_link(new_concept, generator_concept)
    # add_object_to_parents(obj, new_concept, lattice)
    return new_concept

def create_lattice_incrementally(g, m, i):
    bottom = Concept(set(), set(m))
    lattice = Lattice([])
    lattice.add_concept(bottom)

    for obj in g:
        intent = i.image(obj)
        add_intent(obj, intent, bottom, lattice)
    return lattice

def read_relation_from_file(file_path):
    with open(file_path, 'r') as f:
        lines = f.readlines()

    # 读取对象数和属性数
    num_objects, num_attributes = map(int, lines[0].strip().split(','))

    # 读取关系数据
    relation_pairs = []
    for obj_idx, line in enumerate(lines[1:num_objects+1]):
        attributes = list(map(int, line.strip().split(',')))
        for attr_idx, has_attr in enumerate(attributes):
            if has_attr == 1:
                # 对象索引从1开始，属性索引从1开始
                relation_pairs.append((str(obj_idx + 1), chr(ord('a') + attr_idx)))

    return num_objects, num_attributes, relation_pairs

if __name__ == '__main__':
    start = time.time()
    file_path = './experiment04/abalone.txt'
    num_objects, num_attributes, relation_pairs = read_relation_from_file(file_path)
    rel = Relation(relation_pairs)
    # 自动生成对象数组名和属性数组名
    object_names = ['{}'.format(i + 1) for i in range(num_objects)]
    attribute_names = ['{}'.format(chr(97 + i)) for i in range(num_attributes)]
    l = create_lattice_incrementally(object_names, attribute_names, rel)
    # print(l.concepts)
    print(len(l.concepts))
    print(time.time() - start)
